package 力扣_树算法.二叉树;

import java.util.HashMap;
import java.util.Map;

/**110.平衡二叉树
 * @author zx
 * @create 2022-04-11 10:07
 */
public class Num110 {
    /**
     * 方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。
     * 如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。
     * 自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，
     * 再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），
     * 否则返回−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
     */
    public boolean isBalanced3(TreeNode root) {
        return height(root) >= 0;
    }

    public int height3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        //左子树不平衡 || 右子树不平衡 || 树不是平衡树
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    /**
     * 加入记忆化搜索的自顶向下递归
     */
    public boolean isBalanced4(TreeNode root) {
        //记忆化搜索的思想：
        // 在递归的过程中，若某个节点的高度已经被计算过了，我们使用Map存储该节点以及其高度值，下次
        // 再用到这个节点时，直接从Map中取高度即可，避免多次重复的递归过程
        Map<TreeNode,Integer> map = new HashMap<>();
        if(root == null){
            return true;
        }
        //判断当前以root为根节点的树是否满足平衡条件
        int left = 0;
        int right = 0;
        if(map.containsKey(root.left)){
            //此时左树的高度已经被计算过了,直接从map中取出节点值对应的高度
            left = map.get(root.left);
        }else{
            map.put(root.left,height(root.left));
        }
        if(map.containsKey(root.right)){
            //此时右树的高度已经被计算过了,直接从map中取出节点值对应的高度
            right = map.get(root.right);
        }else{
            map.put(root.right,height(root.right));
        }
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
//    private int height(TreeNode root){
//        if(root == null){
//            return 0;
//        }
//        return 1 + Math.max(height(root.left),height(root.right));
//    }


    /**
     * @return 递归写法二(自顶向下)
     */
    public boolean isBalanced(TreeNode root) {
        //递归拆分子问题：以root为根节点的二叉树左右子树高度差<=1 && 左树是平衡树 && 右树是平衡树
        if(root == null){
            return true;
        }
        return Math.abs(depth(root.left) - depth(root.right)) <= 1&& isBalanced(root.left) && isBalanced(root.right);
    }
    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftDepth = depth(root.left) + 1;
        int rightDepth = depth(root.right) + 1;
        return Math.max(leftDepth,rightDepth);
    }

    /**
     * @return 递归写法一(自顶向下)
     * 此方法容易想到，但会产生大量重复计算，时间复杂度较高。
     */
    public boolean isBalanced1(TreeNode root) {
        //递归拆分子问题：以root为根节点的二叉树左右子树高度差<=1 && 左树是平衡树 && 右树是平衡树
        if(root == null){
            return true;
        }
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(height(root.left),height(root.right));
    }
}
